﻿public class Solution
{
    private IList<IList<int>> result = new List<IList<int>>();
    private IList<int> res = new List<int>();
    
    public IList<IList<int>> CombinationSum(int[] candidates, int target)
    {
        int start = 0;
        trackbacking(candidates, target, start);
        return result;
    }

    private void trackbacking(int[] candidates, int target, int start)
    {
        int sum = res.Sum();
        if (sum == target)
        {
            result.Add(new List<int>(res));
            return;
        }

        if (sum > target) return;

        for (int i = start; i < candidates.Length; i++)
        {
            res.Add(candidates[i]);
            trackbacking(candidates, target, i);
            res.RemoveAt(res.Count-1);
        }
    }

    public static void Main(string[] args)
    {
        int[] candidates = [2, 3, 6, 7];
        int target = 7;
        Solution solution = new Solution();
        IList<IList<int>> result = solution.CombinationSum(candidates, target);

        foreach (IList<int> res in result)
        {
            foreach (int r in res)
            {
                Console.Write($"{r} ");
            }
            Console.WriteLine();
        }
    }
}